package Greedy.leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 1. 问题描述
 *      给定一个数组，它的第i 个元素是一支给定股票第 i 天的价格。
 *      设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
 *      注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）
 *
 * 2. 算法分析
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 买卖股票的最佳时机2 {
    public static void main(String[] args) {
        ArrayList arrayList = new ArrayList();
        Queue<Integer> queue = new LinkedList<>();


    }


    /**
     * 动态规划
     * 如果我们将关注点放置在利润的角度上我们很难写出dp方程，但是我们将角度放置在当前交易的股票状态上
     * 此时分析难度就降低不少，因为第i天交易完成之后我们的股票状态只有两种：有股票，没有股票，所以此时
     * 我们的dp数组因该设置为二维的 dp[len][2],其中,
     *      dp[i][0] 表示第i天交易完成之后的最大利润时，手上没有股票
     *      dp[i][1] 表示第i天交易完成之后的最大利润时，手上有股票
     * 首先我们很容易知道
     *      dp[0][0] = 0 表示第0天没有买进当前的股票
     *      dp[0][1] = -prices[0] 表示第0天买进了当前的股票，此时的利润为负的
     * 对于dp[i][0],我们有两种状态：
     *      首先明确dp[i][0]的含义：第i天交易完成只之后最大利润时，手上没有任何股票
     *      对于第i天交易完成，手上没有股票，有两种情况：
     *          1. 第i-1天有股票，但是在第i天卖出，所以此时的利润为 dp[i-1][1] + prices[i]
     *          2. 第i-1天没有股票，并且第i天没有买进，此时利润就等于dp[i-1][0]
     *  对于dp[i][1]，我们有两种状态：
     *      首先明确dp[i][1]的含义：第i天交易完成之后手上有股票，对于第i天交易完成手上有股票
     *      我们有两种情况：
     *          1. 第i-1天交易完之后有股票，到第i天没有卖出，此时的利润就是 dp[i-1][1]
     *          2. 第i-1天交易完成之后没有股票，到第i天买入当前股票，此时的利润为 dp[i-1][0] - prices[i]
     *  最终我们求得的状态转移方程如下：
     *          dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i])
     *          dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0] - prices[i])
     * @param prices
     * @return
     */
    public static int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0]; // 第0天时买入股票，此时的利润为-prices[0]
        for(int i = 1; i < prices.length; i++) {
            // 1. 第i-1天有股票但是第i天卖掉  2. 第i-1天没有股票
            dp[i][0] = Math.max(dp[i-1][1]+prices[i],dp[i-1][0]);
            // 1. 第i-1天有股票，但是第i天没有卖掉   2. 第i-1天没有股票，但是第i天买进
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
        }
        return dp[prices.length-1][0];
    }
}
